package leetcode.动态规划;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author :songyaozhang
 * @date :Created 2021/8/16 16:19
 * @description :https://leetcode-cn.com/problems/delete-and-earn/
 */
public class 删除并获得点数 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.deleteAndEarn(new int[]{3,4,2}));
    }

    class Solution {

        public int deleteAndEarn(int[] nums) {
            int maxVal = 0;
            for (int num : nums) {
                maxVal = Math.max(maxVal, num);
            }
            int[] sum = new int[maxVal + 1];
            for (int num : nums) {
                sum[num] += num;
            }
            return rob(sum);
        }

        private int rob(int[] nums) {
            int n = nums.length;
            if (n == 0) return 0;
            if (n == 1) return nums[0];
            int[] dp = new int[n];
            dp[0] = nums[0];
            dp[1] = Math.max(nums[0], nums[1]);
            for (int i = 2; i < n; i++) {
                dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
            }
            return dp[n - 1];
        }

    }
}
